package com.klun.project.common.constans.leetcode;

import com.klun.project.common.constans.utils.ParseUtils;

import java.util.List;

// 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
// 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上
// 被小偷闯入，系统会自动报警。
// 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
//
// 示例 1：
//输入：[1,2,3,1]
//输出：4
//解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
//     偷窃到的最高金额 = 1 + 3 = 4 。
//
// 示例 2：
//输入：[2,7,9,3,1]
//输出：12
//解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
//     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
//
// 提示：
// 1 <= nums.length <= 100
// 0 <= nums[i] <= 400
// Related Topics 数组 动态规划


public class Solution198 {

	// f(i) = f(i-2) + n[i]
	public int rob(int[] nums) {
		if (nums.length == 0) return 0;
		if (nums.length == 1) return nums[0];
		int max0 = nums[0];
		int max1 = Math.max(nums[0], nums[1]);
		int temp = 0;
		for (int i = 2; i < nums.length; i++) {
			temp = max1;
			max1 = Math.max(max0 + nums[i], max1);
			max0 = temp;
		}
		return Math.max(max0, max1);
	}

	public static void main(String[] args) {
		Solution198 solution = new Solution198();
		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
//		System.out.println(solution.rob(new int[]{2, 7, 9, 3, 1}));
		System.out.println(solution.rob(new int[]{1, 3, 1, 3, 100}));
	}

}
